package week06

import "math"

// 188. 买卖股票的最佳时机 IV
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

func maxProfit(k int, prices []int) int {
	var dp = make([][][]int, len(prices)+1)
	for i := range dp {
		dp[i] = make([][]int, 2)
		for j := range dp[i] {
			dp[i][j] = make([]int, k+1)
			for c := range dp[i][j] {
				dp[i][j][c] = math.MinInt32
			}
		}
	}
	dp[0][0][0] = 0
	for i := 1; i <= len(prices); i++ {
		for j := 0; j <= 1; j++ {
			for c := 0; c <= k; c++ {
				dp[i][j][c] = dp[i-1][j][c]
				if j == 0 {
					dp[i][0][c] = max(dp[i][0][c], dp[i-1][1][c] + prices[i-1])
				} else if c > 0 {
					dp[i][1][c] = max(dp[i][1][c], dp[i-1][0][c-1] - prices[i-1])
				}
			}
		}
	}
	var ans = 0
	for c := 0; c <= k; c++ {
		ans = max(ans, dp[len(prices)][0][c])
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}